\subsection{ElGamal Signaturverfahren}
Die Sicherheit beim ElGamal Signaturverfahren beruht auf der Schwierigkeit, diskrete Logarithmen in \((\mathbb{Z}/p\mathbb{Z})^*\) zu berechnen. Anders als beim RSA-Verfahren
lässt sich die Ver- und Entschlüsselung beim ElGamal-Verfahren nicht vertauschen, weshalb das Signaturverfahren anders als das Verschlüsselungsverfahren konstruiert ist.

\subsubsection{Schlüsselerzeugung \buchmann{13.5.1}}
Zur Schlüsselerzeugung wählt Alice eine zufällige große Primzahl $p$ und eine Primitivwurzel $g$ mod $p$. 
Dann wählt sie zufällig $a$ in der Menge $\lbrace1, 2, \ldots, p-2 \rbrace $ und berechnet $A = g^a \mod{p}$.
Der private Schlüssel ist $a$ und der öffentliche Schlüssel ist $(p,g,A)$.

\subsubsection{Erzeugung der Signatur \buchmann{13.5.2}}
Ein Text $m\in\lbrace0,1\rbrace^*$ wird von Alice signiert. Dazu wird eine öffentlich bekannte, kollisionsresistente Hashfunktion
$$ h:\lbrace0,1\rbrace^*\rightarrow\lbrace1,2,\ldots,p-2\rbrace$$ 
verwendet. Zusätzlich dazu wählt sie zufällig eine Zahl $k\in\lbrace1,2,\ldots,p-2\rbrace$, für die $\gcd(k,p-1)=1$ gilt.
Zur Erzeugung der Signatur werden folgende Berechnungen durchgeführt:
$$r=g^k\mod{p}$$
$$s=k^{-1}(h(m)-ar)\mod{(p-1)}$$
Die Signatur ist das Paar $(r,s)$. Zur Verifikation wird zusätzlich $m$ benötigt, da eine Hashfunktion verwendet wurde und der Empfänger aus $s$ nicht $m$ ermitteln kann.

\subsubsection{Verifikation \buchmann{13.5.3}}
Zur Verifikation wird der öffentliche Schlüssel $(p,g,A)$ benötigt. Zusätzlich dazu muss sich der Empfänger von der Authentizität von diesem überzeugen.
Zunächst überprüft der Empfänger, ob
$$1\leq{r}\leq{p-1}$$
gilt. Wenn nicht, wird die Signatur abgewiesen. Ansonsten wird die Verifikationskongruenz überprüft:
$$A^rr^s\equiv g^{h(m)}\mod{p}$$
Ist diese erfüllt, wird die Signatur akzeptiert.
Es kann gezeigt werden, dass die Verifikation funktioniert, wenn $s$ konstruiert wurde, wie beschrieben. Zur Erinnerung:
$$A=g^a\mod{p},\qquad r=g^k\mod{p},\qquad s=k^{-1}(h(m)-ar)\mod{(p-1)}$$
$$A^rr^s\equiv g^{ar}g^{kk^{-1}(h(m)-ar)}\equiv g^{ar}g^{h(m)-ar} \equiv g^{ar+h(m)-ar} \equiv g^{h(m)}\mod{p}$$
Wenn $A^rr^s\equiv g^{h(m)}\mod{p}$ für ein Paar $(r,s)$ erfüllt ist und $k$ der diskrete Logarithmus von $r$ zur Basis $g$ ist, gilt unter Berücksichtigung von Korollar 3.9.3\buchmann{3.9}:
$$A^rr^s\equiv g^{ar+ks}\equiv g^{h(m)}\mod{p}$$
Zur Erinnerung Korollar 3.9.3 mit $g\in G$ und den ganzen Zahlen $k,l$. Es gilt $g^l=g^k$ genau dann, wenn $l\equiv k\mod{\order{g}}$.
Da $g$ eine Primitivwurzel mod $p$ ist, ist $\order{g}=p-1$ und es gilt:
$$ar+ks\equiv h(m)\mod{(p-1)}$$
Wenn $\gcd{(k,p-1)}=1$ gilt, folgt durch Umstellung die Berechnungsformel für $s$.
\subsubsection{Beispiel}
Alice wählt $p=23$, $g=7$, $a=6$ und berechnet damit $A=g^a\mod{p}=4$. Der öffentliche Schlüssel $(p,g,A)$ ist also $(23,7,6)$ und der geheime Schlüssel $a$ ist $6$.
Ein Dokument $m$ soll signiert werden. Der Hashwert dieses Dokuments sei $h(m)=7$. Dann wird $k=5$ gewählt und damit $r=17$ berechnet. Zusätzlich muss das Inverse von $k\mod{(p-1)}$ berechnet werden, 
in diesem Fall also das Inverse von $5\mod{22}$. Nach Berechnung ergibt sich $k^{-1}=9$. Mit diesen Werten lässt sich $s$ berechnen:
$$s=k^{-1}(h(m)-ar)\mod{(p-1)}=9*(7-6*17)\mod{22}=3$$
Damit ergibt sich für die Signatur $(r,s)$ der Wert $(17,3)$.
Zur Verifikation muss die Verifikationskongruenz $A^rr^s\mod{p}$ vom Empfänger berechnet werden.
$$4^{17}*17^3\mod{23}=5$$
Zusätzlich berechnet der Empfänger $g^{h(m)}\mod{p}$:
$$7^7\mod{23}=5$$
Da die beiden Werte übereinstimmen ist die Signatur verifiziert.
\subsubsection{Wahl von k \buchmann{13.5.5}}
Aus Sicherheitsgründen muss für jede Signatur ein neuer Exponent $k$ gewählt werden, was bei zufälliger Wahl von $k$ garantiert ist.
Falls dennoch das selbe $k$ für zwei Signaturen verwendet wird, ist der Wert $r$ für beide Signaturen gleich.
Dann gilt folgendes:
$$s\textsubscript{1}\equiv k^{-1}(h(m\textsubscript{1})-ar)\mod{(p-1)}$$
$$s\textsubscript{2}\equiv k^{-1}(h(m\textsubscript{2})-ar)\mod{(p-1)}$$
Damit lässt sich $k^{-1}$ berechnen:
$$s\textsubscript{1}-s\textsubscript{2}\equiv k^{-1}(h(m\textsubscript{1})-ar)-k^{-1}(h(m\textsubscript{2})-ar)\mod{(p-1)}$$
$$s\textsubscript{1}-s\textsubscript{2}\equiv k^{-1}(h(m\textsubscript{1})-ar -(h(m\textsubscript{2})-ar))\mod{(p-1)}$$
$$s\textsubscript{1}-s\textsubscript{2}\equiv k^{-1}(h(m\textsubscript{1})-ar - h(m\textsubscript{2})+ar)\mod{(p-1)}$$
$$s\textsubscript{1}-s\textsubscript{2}\equiv k^{-1}(h(m\textsubscript{1})-h(m\textsubscript{2}))\mod{(p-1)}$$
Wenn $h(m\textsubscript{1})-h(m\textsubscript{2})$ invertierbar in mod $(p-1)$ ist, lässt sich $k^{-1}$ berechnen. Anschließend lässt sich $k$ als das Inverse von $k^{-1}$ berechnen.
Mit $k,s\textsubscript{1},r,h(m\textsubscript{1})$ lässt sich abschließend der geheime Schlüssel $a$ berechnen:
$$s\textsubscript{1}\equiv k^{-1}(h(m\textsubscript{1})-ar)\mod{(p-1)}$$
$$s\textsubscript{1}k\equiv h(m\textsubscript{1})-ar\mod{(p-1)}$$
$$ar\equiv h(m\textsubscript{1})-s\textsubscript{1}k\mod{(p-1)}$$
$$a\equiv r^{-1}(h(m\textsubscript{1})-s\textsubscript{1}k)\mod{(p-1)}$$
Da $r$ bekannt ist, lässt sich auch das Inverse davon berechnen. Mit $r^{-1}$ lässt sich $a$ berechnen.
\subsubsection{Existenzielle Fälschung \buchmann{13.5.6}}
Es ist wichtig, dass beim ElGamal Signaturverfahren eine Hashfunktion verwendet wird und dieser Wert anstelle des Originaldokuments signiert wird. Beim Signieren der Nachricht $x$ ohne
Hashfunktion, gilt folgende Verifikationskongruenz:
$$A^rr^s\equiv g^m\mod{p}$$
Für diese Kongruenz kann man $r,s$ und $m$, also die Signatur und die Nachricht, so wählen, dass die Kongruenz erfüllt ist. Dadurch lassen sich gefälschte Nachrichten mit einer gültigen Signatur erstellen.
Dafür müssen zwei ganze Zahlen $u$ und $v$ gewählt werden, wobei $\gcd{(v,p-1)} = 1$ gelten muss. Die Werte werden wie folgt gewählt:
$$r=g^uA^v\mod{p},\qquad	s=-rv^{-1}\mod{(p-1)},\qquad	m=su\mod{(p-1)}$$
Setzt man die Werte in die Verifikationskongruenz ein, erhält man:
$$A^rr^s\equiv A^rg^{su}A^{sv}\equiv A^rg^{su}A^{-r}\equiv g^{su}\equiv g^m\mod{p}$$
Wenn Hashfunktionen verwendet werden können sich Angreifer nur Signaturen von Hashwerten erzeugen lassen. Dabei lässt sich der Klartext nicht zurückgewinnen, wenn die 
Hashfunktion eine Einwegfunktion ist.\par
Eine weitere Möglichkeit zur Erstellung einer existenziellen Fälschung ergibt sich, wenn die Bedingung $1\leq r\leq p-1$ nicht gefordert ist.
In dem Fall lässt sich aus bekannten Signaturen eine neue Signatur erstellen. Mit der Signatur $(r,s)$ für die Nachricht $m$ lässt sich eine Signatur für die Nachricht $m'$ berechnen.
Zunächst wird unter der Voraussetzung, dass $h(m)\mod{(p-1)}$ invertierbar ist, der Wert $u$ berechnet:
$$u=h(m')h(m)^{-1}\mod{(p-1)}$$
Außerdem wird $s'$ wie folgt berechnet:
$$s'=su\mod{(p-1)}$$
Unter Anwendung des chinesischen Restsatzes wird ein $r'$ berechnet:
$$r'\equiv ru\mod{(p-1)}, r'\equiv r\mod{p}$$
Das Paar $(r',s')$ ist die Signatur der Nachricht $m'$. Die Verifikationskongruenz funktioniert mit der berechneten Signatur:
$$A^{r'}(r')^{s'}\equiv A^{ru}r^{su}\equiv (g^{a})^{ru}(g^{k})^{su} \equiv g^{aru}g^{ksu}\equiv g^{aru+ksu}\equiv g^{u(ar+ks)}\equiv g^{uh(m)} \equiv g^{h(m')}\mod{p}$$
Mit $u=h(m')h(m)^{-1}\mod{(p-1)}$ wird deutlich, dass auch diese Verifikationskongruenz erfüllt ist:
$$g^{h(m')h(m)^{-1}h(m)}\equiv g^{h(m')}\mod{p}$$
Die Verifikationskongruenz ist erfüllt, jedoch wird der Test $1\leq r'\leq p-1$ verletzt. Es gilt:
$$1\leq r\leq p-1,	r\equiv r'\mod{p}$$
Es gilt jedoch auch:
$$r'\equiv ru\not\equiv r\mod{(p-1)} $$
Dies ergibt sich aus der Tatsache, dass $h$ eine kollisionsresistente Hashfunktion ist und folgendes gilt:
$$u\equiv h(m')h(m)^{-1}\not\equiv 1\mod{(p-1)}$$
Daher gilt $r\not= r'$ und es folgt $r'\geq p$. Wenn $r'\leq(p-1)$ wäre müsste $r'=r$ gelten, da $r\equiv r'\mod{p}$ und $0\leq r'\leq (p-1)$ gelten müssen, was jedoch durch $r'\not\equiv r\mod{(p-1)}$ verletzt wird.

